import random
def xier(lst):
    """希尔排序"""
    n=len(lst)
    p=int(n/2)
    while p>0:
        for i in range(p,n):
            t=lst[i]
            j=i
            while j>=p and lst[j-p]>t:
                lst[j]=lst[j-p]
                j=j-p
            lst[j]=t
        p=p//2
    return lst


lst=[3,67,32,88,46,39,73]
# print(xier(lst))

def fast(lst,min,max):
    i=min-1
    p=lst[max]
    for j in range(min, max):
        if lst[j]<=p:
            i=i+1
            lst[i],lst[j]=lst[j],lst[i]
    lst[i+1],lst[max]=lst[max],lst[i+1]
    return(i+1)

def sort(lst,min,max):
    if min<max:
        p=fast(lst,min,max)
        sort(lst,min,p-1)
        sort(lst,p+1,max)
    return lst
for i in range(10):
    random.shuffle(lst)
    print(lst)
    n=len(lst)
    print("end====>", sort(lst,0,n-1))




